/*
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules.uniqueness;

import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.onegravity.sudoku.solver.HintResource;
import com.onegravity.sudoku.solver.R;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHint;
import com.onegravity.sudoku.solver.core.IndirectHintProducer;
import com.onegravity.sudoku.solver.data.Block;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.util.BitSetIterator;
import com.onegravity.sudoku.solver.util.BitSetFactory;

/**
 * Implementation of the Avoidable Rectangle solving technique.
 * Supports type 1 and 2.
 */
public class AvoidableRectangleProducer implements IndirectHintProducer {

	@Override
    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {

		if (grid.hasExtraRegions()) return;
		
		// (1) find empty cell with at least 2 candidates (Cell D)
		BitSetIterator<Integer> it = new BitSetIterator<Integer>();
        for (int y=0; y<9; y++) {
            for (int x=0; x<9; x++) {
                Cell cellD = grid.getCell(x, y);
                BitSet potentialsD = cellD.getPotentialValues();
                if (cellD.isEmpty() && potentialsD.cardinality()>=2) {
                	for (it.restart(potentialsD); it.hasNext(); ) {
                        findRectangle(grid, accu, cellD, it.next());
                	}
                }
            }
        }
    }
	
	/**
	 * Find Rectangle
	 * 
	 *  Avoidable Rectangle Type 1:
	 *   Cell A (a)		Cell B (b)
	 *   Cell C (b)		Cell D (ax+)
	 *    
	 *  Avoidable Rectangle Type 2:
	 *   Cell A (a)		Cell B (b)
	 *   Cell C (bx)	Cell D (ax -> bivalue cell)
	 */
	private void findRectangle(Grid grid, HintsAccumulator accu, Cell cellD, int a) throws InterruptedException, StopHintProductionException {
        // (2) find opposite corner of Cell D -> Cell A:
        //	- must be within specific row or column range
        //	- must be in different block, row and column
        //	- mustn't be empty
        //	- mustn't be a given
        //	- must be value a
        Block cellDBlock = (Block) grid.getRegionAt(Block.class, cellD);
        int cellDBlockCode = cellDBlock.getBlockCode();
        int cellD_x = cellD.getX();
        int cellD_y = cellD.getY();
        int minCol = cellD_x/3*3;
        int maxCol = minCol+2;
        int minRow = cellD_y/3*3;
        int maxRow = minRow+2;
        for (int yPos=0; yPos<9; yPos++) {
            for (int xPos=0; xPos<9; xPos++) {
                if (Thread.interrupted()) throw new InterruptedException();
            	if ((yPos>=minRow && yPos<=maxRow) || (xPos>=minCol && xPos<=maxCol)) {
	                Cell cellA = grid.getCell(xPos, yPos);
	                Block cellABlock = (Block) grid.getRegionAt(Block.class, cellA);
	                int cellAValue = cellA.getValue();
	                int cellABlockCode = cellABlock.getBlockCode();
	                if (!cellA.isEmpty() && !cellA.isGiven() && cellAValue==a &&
	                	cellABlockCode!=cellDBlockCode && yPos!=cellD_y && xPos!=cellD_x) {
	                    // (3) retrieve other corners (Cell B and Cell C)
	                	Cell cellB = grid.getCell(cellD.getX(), yPos);
	                	Cell cellC = grid.getCell(xPos, cellD.getY());
	                	Block cellBBlock = (Block) grid.getRegionAt(Block.class, cellB);
	                    int cellBBlockCode = cellBBlock.getBlockCode();
	                	Block cellCBlock = (Block) grid.getRegionAt(Block.class, cellC);
	                    int cellCBlockCode = cellCBlock.getBlockCode();
	                	if ( (cellABlockCode==cellBBlockCode && cellCBlockCode==cellDBlockCode) ||
	                		 (cellABlockCode==cellCBlockCode && cellBBlockCode==cellDBlockCode)) {
		                	IndirectHint hint = isRectangleValid(cellA, cellB, cellC, cellD, a);
		                	if (hint!=null && hint.isWorth()) accu.add(hint);
	                	}
	                }
            	}
            }
        }
	}
	
	/**
	 * Checks whether the rectangle is a valid Avoidable Rectangle
	 * and creates an according hint (null if no AR was found).
	 * 
	 *  Avoidable Rectangle Type 1:
	 *   Cell A (a)		Cell B (b)
	 *   Cell C (b)		Cell D (ax -> bivalue cell)
	 *    
	 *  Avoidable Rectangle Type 2:
	 *   Cell A (a)		Cell B (b)
	 *   Cell C (bx)	Cell D (ax -> bivalue cell)
	 */
	private IndirectHint isRectangleValid(Cell cellA, Cell cellB, Cell cellC, Cell cellD, int a) {
		if (cellB.isEmpty() || cellC.isEmpty()) {
			// test for Type 2:
			// - Cell D must be a bivalue cell
			// - Cell B mustn't be empty, mustn't be a given and must be b (!= any candidate in cell D)
			// - Cell C must be a bivalue cell and contain the candidates b and x (x is the second candidate in cell D)
			if (cellB.isEmpty()) {
				Cell tmp = cellB;
				cellB = cellC;
				cellC = tmp;
			}
			BitSet candidatesD = cellD.getPotentialValues();
			int x = candidatesD.nextSetBit(0);
			if (x==a) x = candidatesD.nextSetBit(a+1);
			int b = cellB.getValue();
			BitSet candidatesC = cellC.getPotentialValues();
			if (candidatesD.cardinality()==2 &&
				!cellB.isEmpty() && !cellB.isGiven() && !candidatesD.get(b) &&
				cellC.isEmpty() && candidatesC.cardinality()==2 && candidatesC.get(b) && candidatesC.get(x)) {
				// Avoidable Rectangle Type 2 found
	        	Map<Cell, BitSet> removablePotentials = getRemovablePotentials(cellC, cellD, x);
		        List<Cell> rectangle = Arrays.asList(new Cell[] {cellA, cellB, cellC, cellD});
	        	IndirectHint hint = new AvoidableRectangleHint(rectangle, a, b, x, removablePotentials);
	        	if (hint.isWorth()) return hint;
			}
		}
		else {
			// test for Type 1:
			// - cells B and C mustn't be givens and both must be b
			// - b mustn't be any of the candidate in cell D
			int valueB = cellB.getValue();
			int valueC = cellC.getValue();
			if (!cellB.isEmpty() && !cellB.isGiven() && !cellC.isEmpty() && !cellC.isGiven() &&
				valueB==valueC && !cellD.getPotentialValues().get(valueB)) {
				// Avoidable Rectangle Type 1 found
				Map<Cell,BitSet> removablePotentials = new HashMap<Cell,BitSet>();
			    removablePotentials.put(cellD, BitSetFactory.createOneElement(a));
		        List<Cell> rectangle = Arrays.asList(new Cell[] {cellA, cellB, cellC, cellD});
		        IndirectHint hint = new AvoidableRectangleHint(rectangle, a, valueB, removablePotentials);
	        	if (hint.isWorth()) return hint;
			}
		}
		return null;
	}

    private Map<Cell,BitSet> getRemovablePotentials(Cell cellC, Cell cellD, int x) {
        // Build list of removable potentials
        Map<Cell,BitSet> removablePotentials = new HashMap<Cell,BitSet>();
        Set<Cell> victims = new LinkedHashSet<Cell>(cellD.getHouseCells());
        victims.retainAll(cellC.getHouseCells());
        BitSet xBitSet = BitSetFactory.createOneElement(x);
        for (Cell cell:victims) {
            if (cell.hasPotentialValue(x))
                removablePotentials.put(cell, xBitSet);
        }
        return removablePotentials;
    }

	@Override
	public String getProducerName() {
		return HintResource.getString(R.string.producer_avoidable_rectangles);
	}
}